package com.zp.self.module.level_4_算法练习.算法.排序.算法题;
import org.junit.Test;

import java.util.Arrays;

/**
 * @author By ZengPeng
 */
public class 力扣_1005_K次取反后最大化的数组和{
    @Test
    public void main() {
        
        Solution solution = new 力扣_1005_K次取反后最大化的数组和 ().new Solution();
        System.out.println(solution.largestSumAfterKNegations(new int[]{-8,3,-5,-3,-5,-2},6));
    }

    /**
     题目：给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
         选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
         重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
         以这种方式修改数组后，返回数组 可能的最大和 。

         示例 1：
         输入：nums = [4,2,3], k = 1
         输出：5
         解释：选择下标 1 ，nums 变为 [4,-2,3] 。

         示例 2：
         输入：nums = [3,-1,0,2], k = 3
         输出：6
         解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

         示例 3：
         输入：nums = [2,-3,-1,5,-4], k = 2
         输出：13
         解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。


     分析：【P 💖💖💖】
        1.排序：找到负数的开始下标，是否存在0？
                --执行用时：2 ms, 在所有 Java 提交中击败了97.67%的用户
                --编码耗时:[超过30分钟]

     边界值 & 注意点：
        1.
     **/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int index=0,sum=0;
        while (k>0 && index<nums.length){
            if(nums[index]<0){
                sum-=nums[index++];
            }else if(nums[index]==0 || (k&1)==0){
                sum+=nums[index++];
                break;
            }else {
                if(index==0 || nums[index]+nums[index-1]<0){//第一个正数  小于 第一个负数绝对值
                    sum-=nums[index++];
                }else {//第一个正数  大于 第一个负数绝对值
                    sum=sum+2*nums[index-1]+nums[index++];
                }
                break;
            }
            k--;
        }
        if(index == nums.length && (k&1)!=0 && nums[index-1]<0){
            sum+=2*nums[index-1];
        }
        while (index<nums.length){
            sum+=nums[index++];
        }
        return sum;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}